#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
	int data;
	struct node *next;
} node_t ;

void create_circle_2(node_t **head)
{
	node_t *new;

	new = (node_t *)malloc(sizeof(node_t));
	memset(new, 0, sizeof(new));
	new->data = 1;

	*head = new;
	new->next = *head;
}

void create_circle(node_t **head)
{
	int i, n = 23, m = 12;
	node_t *new, *end, *circle;

	for (i = 0; i < n; i++) {
		new = (node_t *)malloc(sizeof(node_t));
		memset(new, 0, sizeof(new));
		new->data = i;

		if (!*head) {
			*head = new;
			end = new;
			continue;
		}
		new->next = *head;
		*head = new;
		if (i == m)
			circle = new;
	}
	end->next = circle;

}
inline void print_list(node_t *n)
{
	while (n!=NULL) {
		printf("%d ", n->data);
		n = n->next;
	}
	printf("\n");
}

int check_circle(node_t *h, node_t **pos)
{
	node_t *p = NULL, *q = NULL; /*p: 1 step, q: 2 step */
	*pos = NULL;

	p = h;
	if (h && h->next)
		q = h->next->next;
	while (1) {
		if (p == q)
			break;
		p = p->next;
	
		q = q->next;
		if (q && (q = q->next))
			continue;
		break;
	}
	
	if (q == NULL || p == NULL) {
		printf("ret:%d\n", 0);
		return 0;
	}
	*pos = p;
	printf("ret:%d:data:%d\n", 1, p->data);
	return 1;
}

void find_cross(node_t *h1, node_t *pos)
{
	node_t *h2, *p, *tmp, *q1, *q2;
	int l1 = 0, l2 = 0, d;

	h2 = pos->next;
	pos->next = NULL;

	q1 = h1;
	while (q1 != NULL) {
		q1 = q1->next;
		l1 ++;
	}
	q2 = h2;
	while (q2 != NULL) {
		q2 = q2->next;
		l2 ++;
	}
	
	if (l1 == l2) {
		p = pos; 
		printf("pos:%d\n", p->data);
		return;
	}
	
	if (l1 > l2) {
		d = l1 - l2;
	} else {
		d = l2 - l1;
		tmp = h1;
		h1 = h2;
		h2 = tmp;
	}
	while(d--) {
		h1 = h1->next;
	}
	while (h1 != h2) {
		h1 = h1->next;
		h2 = h2->next;
	}
	p = h1;
	printf("pos:%d\n", p->data);

}

int main()
{
	node_t *head = NULL, *pos;

	create_circle(&head);
//	print_list(head);
	check_circle(head, &pos);
	find_cross(head, pos);

//	check_circle(NULL);
	create_circle_2(&head);
	check_circle(head, &pos);
	find_cross(head, pos);

	return 0;
}
